package com.learn.algorithm.exercises.nowcoder;

/**
 * @author wangxing
 * @version 2020/5/28 20:05 Administrator
 */
public class KuaiShou {
    /**
     * 小明最近在做病毒自动检测，他发现，在某些library 的代码段的二进制表示中，
     * 如果包含子串并且恰好有k个1，就有可能有潜在的病毒。library的二进制表示可能很大，
     * 并且子串可能很多，人工分析不可能，于是他想写个程序来先算算到底有多少个子串满足条件。
     * 如果子串内容相同，但是开始或者结束位置不一样，则被认为是不同的子串。
     * 注：子串一定是连续的。例如"010"有6个子串，分别是 "0, "1", "0", "01", "10", "010"
     * <p>
     * 输入描述:
     * 第一行是一个整数k，表示子串中有k个1就有可能是病毒。其中 0 <= k <= 1 000 000
     * <p>
     * 第二行是一个字符串，就是library的代码部分的二进制表示。字符串长度 <= 1 000 000。并且字符串中只包含"0"或"1".
     * <p>
     * 输出描述:
     * 输出一个整数，所有满足只包含k个1的子串的个数。
     * <p>
     * 输入例子1:
     * 1
     * 1010
     * <p>
     * 输出例子1:
     * 6
     * <p>
     * 例子说明1:
     * 满足条件的子串有："1", "1", "10", "01", "10", "010".
     */
    public class SubstringFixedLengthNum {
        /**
         * 动态规划思路，当前状态依赖前k个状态并且需维护当前状态为后面服务，
         * 需要k+1空间，但是需要开辟k+2个空间，其中一个空间来消除掉之前状态的值。
         *
         * @param k
         * @param string
         * @return
         */
        public int getSubstringFixedLengthNum(int k, String string) {
            char[] strArr = string.toCharArray();
            int[] dp = new int[k + 2];
            int result = 0;
            dp[0] = 1;
            int num = 0;
            for (char c : strArr) {
                if (c == '1') {
                    num++;
                }
                if (num - k >= 0) {
                    result += dp[(num - k) % (k + 2)];
                }
                dp[(num + 1) % (k + 2)] = 0;
                dp[num % (k + 2)]++;
            }
            return result;
        }

        public int getSubstringFixedLengthNum2(int k, String string) {
            char[] strArr = string.toCharArray();
            int result = 0;
            int length = strArr.length;
            for (char c : strArr) {
                if (c == '1') {
                    result++;
                }
            }
            if (k > result) {
                result = 0;
            } else {
                result = 0;
                int index = 0;
                int count = 0;
                for (int i = 0; i < length; i++) {
                    index = i;
                    count = 0;
                    while (count < k && index < length) {
                        if (strArr[index] == '1' && ++count == k) {
                            result++;
                            index++;
                            break;
                        }
                        index++;
                    }
                    while (index < length && strArr[index] != '1') {
                        result++;
                        index++;
                    }

                }
            }
            return result;
        }

        public int getSubstringNum(int k, String str) {
            int count = 0;
            char[] strArr = str.toCharArray();
            int size = strArr.length;
            if (k > size) {

            } else {
            /*
                符合有k个1子串的可能条件有
                1.字符串长度为k,并且组成内容全部是1
                2.字符串长度n,n>k,在n中有n-k个0
                执行条件
                遍历整个数组,第i个字母向后的字符串中,求其中1的数量,直到n个长度的字符串中出现k+1个1的时候结束一次遍历
                然后从第i+1个字符串向后遍历k个字符串重复第i个字符串的过程
                遍历位置到size-k
            * */
                int oneNum = 0;
                for (int i = 0, temp_index = 0; i < size && temp_index < size; i++) {
                    temp_index = i;
                    oneNum = 0;
                    while (oneNum <= k && temp_index < size) {
                        if (strArr[temp_index] == '1') {
                            oneNum++;
                        }
                        temp_index++;
                    }
                    if (oneNum == k) {
                        count++;
                    }
                    if (temp_index == size) {
                        break;
                    }
                }
            }
            return count;
        }
    }

}
